#include "graph.h"
using namespace std;

Graph::Graph(int V)
{
    //初始化点数
    this->V=V;
    //新建二维矩阵保存各点
    this->matrix=new int*[V];
    for(int i=0;i<V;i++)
    {
        matrix[i]=new int[V];
        //memset(matrix[i],0,sizeof(matrix[i]));
        for(int j=0;j<V;j++)
            matrix[i][j]=0;
    }
    color=new int[V];
    pai=new int[V];
    disc=new int[V];
    finish=new int[V];
    topo=new int[V];
}

Graph::~Graph()
{
    delete color;
    delete pai;
    for(int i=0;i<V;i++)
        delete[] matrix[i];
    delete disc;
    delete finish;
    delete topo;
}
void
Graph::addEdge(int start,int end,int weight)
{
    this->matrix[start][end]=weight;
    //this->matrix[end][start]=weight;
}

bool
Graph::adjecent(int a,int b)
{
    return matrix[a][b]!=0;
}

void
Graph::printMap()
{
    for(int i=0;i<V;i++)
    {
        for(int j=0;j<V;j++)
        {
            cout<<matrix[i][j]<<"\t";
        }
        cout<<endl;
    }
}

void
Graph::DFS_VISIT(int u,bool second)
{
    if(second)
    	cout<<"V"<<u<<" ";
    time++; //时间增加
    disc[u]=time;   //设置当前处理的点的发现时间
    color[u]=GRAY;  //表示正在处理该点
    for(int i=0;i<V;i++) //处理所有邻边
    {
        if(adjecent(u,i))
        {
            if(color[i]==WHITE)
            {
                pai[i]=u;   //设置前驱为当前节点
                DFS_VISIT(i,second);   //递归处理
            }
        }
    }
    color[u]=BLACK;
    time++; //时间增加
    finish[u]=time;//设置完成时间
    if(!second) //第二次处理不应该破坏之前的拓扑序数组
        topo[topoIndex++]=u;    //将完成的点加入到数组中
}

void
Graph::DFS(bool second)
{
    topoIndex=0;    //初始化拓扑排序数组索引
    for(int i=0;i<V;i++)    //初始化原始颜色、前驱
    {
        color[i]=WHITE;
        pai[i]=NIL;
    }
    time=0; //初始化时间
    if(second)  //如果是第二次
    {
        for(int i=0;i<V;i++)
        {   //拓扑序中完成时间是递增的
            if(color[topo[V-i-1]]==WHITE)
            {//如果这个点没有处理到
                cout<<"分量组：";
                DFS_VISIT(topo[V-i-1],true);   //处理这个点
                cout<<endl;
            }
        }
    }
    else
    {
        for(int i=0;i<V;i++)
        {
            if(color[i]==WHITE) //如果某个点没有处理到
            DFS_VISIT(i);   //处理这个点
        }
    }
}

void
Graph::printDFS()
{
    cout<<"各点的发现时间为"<<endl;
    for(int i=0;i<V;i++)
        cout<<disc[i]<<" ";
    cout<<endl;
    cout<<"各点的结束时间为"<<endl;
    for(int i=0;i<V;i++)
        cout<<finish[i]<<" ";
    cout<<endl;
    cout<<"各点的前驱节点为"<<endl;
    for(int i=0;i<V;i++)
        cout<<pai[i]<<" ";
    cout<<endl;
}

void
Graph::printTopo()
{
    cout<<"拓扑排序结果如下："<<endl;
    for(int i=0;i<V;i++)
    {
        cout<<topo[V-i-1]<<(i==V-1?"\n":"->");
    }
}

void
Graph::transpos()
{
    cout<<"对图进行转置"<<endl;
    for(int i=0;i<V;i++)
    {
        for(int j=0;j<i;j++)
        {
            int t=matrix[i][j];
            matrix[i][j]=matrix[j][i];
            matrix[j][i]=t;
        }
    }
}

